package  main.java.leetcode.editor.cn;
//2022-03-27 16:33:30
//给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。 
//
// 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第
//一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1
//, col + 1) 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
//输出：13
//解释：如图所示，为和最小的两条下降路径
// 
//
// 示例 2： 
//
// 
//
// 
//输入：matrix = [[-19,57],[-40,-5]]
//输出：-59
//解释：如图所示，为和最小的下降路径
// 
//
// 
//
// 提示： 
//
// 
// n == matrix.length == matrix[i].length 
// 1 <= n <= 100 
// -100 <= matrix[i][j] <= 100 
// 
// Related Topics 数组 动态规划 矩阵 
// 👍 156 👎 0

class MinimumFallingPathSum {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new MinimumFallingPathSum().new Solution();
        int[][] test = {{2,1,3},{6,5,4},{7,8,9}};
        solution.minFallingPathSum(test);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        //初始化dp数组第一排元素
        for(int i = 0;i<n;i++){
            dp[0][i] = matrix[0][i];
        }
        for(int i = 1;i<n;i++){
            for(int j = 0;j<n;j++){
                //每一行开头第一个元素
                if(j == 0){
                    dp[i][j] = Math.min(matrix[i][j]+dp[i-1][j],matrix[i][j]+dp[i-1][j+1]);
                    continue;
                }
                //每行最后一个元素
                if(j == n-1){
                    dp[i][j] = Math.min(matrix[i][j]+dp[i-1][j],matrix[i][j]+dp[i-1][j-1]);
                    continue;
                }
                int min = Integer.MAX_VALUE;  //找到当前dp数组上一层可能存在点的最小值
                for(int index = j-1;index<=j+1;index++){
                    if(min>=dp[i-1][index]){
                        min = dp[i-1][index];
                    }
                }
                dp[i][j] = min+matrix[i][j];
            }
        }
        int minDp = Integer.MAX_VALUE;
        for(int i = 0;i<n;i++){
            if(minDp>=dp[n-1][i]){
                minDp = dp[n-1][i];
            }
        }
//        for (int i = 0;i<n;i++){
//            for(int j = 0;j<n;j++){
//                System.out.print(dp[i][j]+"  ");
//            }
//            System.out.println();
//        }
        return minDp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
